The present invention relates to compressing and decompressing data. More particularly, the present invention relates to reducing the number of writes in a memory device by compressing and/or decompressing data. The present invention also relates to lossless compression and decompression of data.
Wear leveling refers to a technique for prolonging a useful life of non-volatile memories such as Flash memories, EPROM (Erasable Programmable Read-Only Memory), PCM (Phase-Change Memory), etc. Non-volatile memories have erasable segments, each of which can sustain a limited number of erases before becoming unreliable. For example, a segment of NAND-flash memory device becomes unusable between 10,000 erases and 1,000,000 erases. A wear leveling attempts to arrange data so that erasures and re-writes are distributed evenly across the memory devices. In the way, a single segment does not permanently fail due to a number of writes and erases only directed to the single segment.
In a computing device, a cache line refers to a smallest amount of data that can be transferred between a main memory and a cache memory. Rather than reading from or writing to a single word or byte from a main memory at a time, each cache line entry usually holds a certain number of words, e.g., multiple addressable entries. Typically, whole contents of a cache line are read or written to and cached at once. A size of a cache line usually varies from 8 bytes to 512 bytes.
Though a traditional solution utilizes the wear leveling to prolong a useful life of a non-volatile memory, the traditional solution does not try to control the number of writes to minimize degradation of the memory or increase the useful life of the non-volatile memory.
A memory subsystem refers to RAM (Random Access Memory), Single Access Memory (e.g., Single Data Rate Synchronous Dynamic Random Access Memory (SDR-SDRAM) which transfers data only one clock transition), and Dual Access Memory (e.g., Double Data Rate Synchronous Dynamic Random Access Memory (DDR SDRAM) which transfers data on a rising and falling edge of a clock signal thus achieves nearly twice bandwidth of the Single Access Memory).
A storage subsystem refers to a set of components implemented for permanently storing data or programs in a computer. The term “permanent” is used to contrast the storage subsystem from the memory subsystem which holds data temporarily—until the user turns off the computer. The storage subsystem comprises at least one storage device (e.g., hard disk, optical disk, floppy disk, tape drive, magnetic disk, etc.) and a storage device controller (e.g., IDE (Integrated Drive Electronics) interface controller which connect a storage device to a computer).
A lossless data compression/decompression technique refers to a data compression/decompression algorithm that enables the original data to be reconstructed from its compressed version. The lossless data compression/decompression is used in a lot of applications. For example, the lossless data compression/decompression is used in a popular Winzip® application and Unix® gzip (GNU zip) application. Especially, the lossless data compression/decompression is used when it is important that an original data and a decompressed version data be identical.
To decompress a portion of a compressed data stream, traditional lossless data compression/decompression methods needs to start a decompression, e.g., using a LZ77 or LZ78 algorithm, at a beginning of an input data stream and to proceed the decompression to an end of the portion of interest of the compressed data stream. Thus, the traditional lossless data compression/decompression methods cannot decompress anything from an arbitrary location (e.g., a middle of compressed data stream) unless the decompression starts from the beginning of the compressed data stream. The LZ77 algorithm is described at J. Ziv et al., “A Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory, 23(3), 1977, incorporated by reference as set forth herein. LZ78 algorithm is described at Estman, et al., U.S. Pat. No. 4,464,650, incorporated by reference as set forth herein.
Thus, it is desirable to prolong a useful life of a non-volatile memory by reducing the number of writes in the non-volatile memory. Thus, it is also highly desirable to provide a system and method that enables a lossless decompression at any location of a compressed data stream.